/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/valid-palindrome-ii
   @Language: C++
   @Datetime: 19-06-17 10:17
   */

class Solution {
	bool isPalindrome(string &s, bool isi){
		int diff=0;
		for(int i=0, j=s.length()-1; i<j && diff<2;)
			if(s[i]==s[j]) ++i, --j;
			else ++diff, isi?++i:--j;
		return diff<2;
	}
public:
	/**
	 * @param s: a string
	 * @return bool: whether you can make s a palindrome by deleting at most one character
	 */
	bool validPalindrome(string &s) {
		// Write your code here
		return isPalindrome(s,true)||isPalindrome(s,false);
	}
};
